// #include "rbtree.h"
// #include <stdio.h>
// #include <stdlib.h>
// #include <string.h>

// /**
// #define DECL_CMP_BY_KEY(KTYPE, VTYPE) \
//   inline static int cmp_pair_KTYPE_VTYPE(pair_KTYPE_VTYPE lhs, pair_KTYPE_VTYPE rhs) {
//     return lhs.first - rhs.first;
//   }
// **/

// cerr_code rbtree_TYPE_init(rbtree_TYPE* tree) {
//   tree->nil = (rbtree_TYPE_node*)malloc(sizeof(rbtree_TYPE_node));;
//   tree->nil->color = COLOR_BLACK;
//   tree->root = tree->nil;
//   return EOK;
// }

// rbtree_TYPE* rbtree_TYPE_new() {
//   rbtree_TYPE *tree = (rbtree_TYPE *)malloc(sizeof(rbtree_TYPE));
//   if (NULL == tree) {
//     return tree;
//   }
//   rbtree_TYPE_init(tree);
//   return tree;
// }

// void _rbtree_TYPE_cleanup(rbtree_TYPE_node* root) {
//   if (root == NULL) {
//     return;
//   }
//   _rbtree_TYPE_cleanup(root->left);
//   _rbtree_TYPE_cleanup(root->right);
//   // free(root);
// }
// cerr_code rbtree_TYPE_dtor(rbtree_TYPE* tree) {
//   _rbtree_TYPE_cleanup(tree->root);
//   return EOK;
// }

// void rbtree_TYPE_free(rbtree_TYPE* tree) {
//   rbtree_TYPE_dtor(tree);
//   free(tree);
// }
// // 一直走到最左边
// rbtree_TYPE_node *rbtree_TYPE_leftmost(rbtree_TYPE *tree, rbtree_TYPE_node *x) {
//   while (x->left != tree->nil) {
//     x = x->left;
//   }
//   return x;
// }

// // 一直走到最右边
// rbtree_TYPE_node *rbtree_TYPE_rightmost(rbtree_TYPE *tree, rbtree_TYPE_node *x) {
//   while (x->right != tree->nil) {
//     x = x->right;
//   }
//   return x;
// }

// // 严格刚好比自己更大的那个元素
// rbtree_TYPE_node *rbtree_TYPE_successor(rbtree_TYPE *tree, rbtree_TYPE_node *x) {
//   rbtree_TYPE_node *y = x->parent;

//   if (x->right != tree->nil) {
//     return rbtree_TYPE_leftmost(tree, x->right);
//   }

//   while ((y != tree->nil) && (x == y->right)) {
//     x = y;
//     y = y->parent;
//   }
//   return y;
// }

// // 左旋
// void rbtree_TYPE_left_rotate(rbtree_TYPE *tree, rbtree_TYPE_node *x) {
//   // 旋转方式
//   // x  --> y  ,  y --> x,   right --> left,  left --> right
//   rbtree_TYPE_node *y = x->right;

//   x->right = y->left;
//   if (y->left != tree->nil) {
//     y->left->parent = x;
//   }

//   y->parent = x->parent;
//   if (x->parent == tree->nil) {
//     tree->root = y;
//   } else if (x == x->parent->left) {
//     x->parent->left = y;
//   } else {
//     x->parent->right = y;
//   }

//   y->left = x;
//   x->parent = y;
// }

// // 右旋
// void rbtree_TYPE_right_rotate(rbtree_TYPE *tree, rbtree_TYPE_node *y) {
//   rbtree_TYPE_node *x = y->left;

//   y->left = x->right;
//   if (x->right != tree->nil) {
//     x->right->parent = y;
//   }

//   x->parent = y->parent;
//   if (y->parent == tree->nil) {
//     tree->root = x;
//   } else if (y == y->parent->right) {
//     y->parent->right = x;
//   } else {
//     y->parent->left = x;
//   }

//   x->right = y;
//   y->parent = x;
// }

// void rbtree_TYPE_insert_node_fixup(rbtree_TYPE *tree, rbtree_TYPE_node *z) {
//   while (z->parent->color == COLOR_RED) { // z ---> COLOR_RED
//     if (z->parent == z->parent->parent->left) {
//       rbtree_TYPE_node *y = z->parent->parent->right;
//       if (y->color == COLOR_RED) {
//         z->parent->color = COLOR_BLACK;
//         y->color = COLOR_BLACK;
//         z->parent->parent->color = COLOR_RED;

//         z = z->parent->parent; // z --> COLOR_RED
//       } else {
//         if (z == z->parent->right) {
//           z = z->parent;
//           rbtree_TYPE_left_rotate(tree, z);
//         }
//         z->parent->color = COLOR_BLACK;
//         z->parent->parent->color = COLOR_RED;
//         rbtree_TYPE_right_rotate(tree, z->parent->parent);
//       }
//     } else {
//       rbtree_TYPE_node *y = z->parent->parent->left;
//       if (y->color == COLOR_RED) {
//         z->parent->color = COLOR_BLACK;
//         y->color = COLOR_BLACK;
//         z->parent->parent->color = COLOR_RED;

//         z = z->parent->parent; // z --> COLOR_RED
//       } else {
//         if (z == z->parent->left) {
//           z = z->parent;
//           rbtree_TYPE_right_rotate(tree, z);
//         }
//         z->parent->color = COLOR_BLACK;
//         z->parent->parent->color = COLOR_RED;
//         rbtree_TYPE_left_rotate(tree, z->parent->parent);
//       }
//     }
//   }

//   tree->root->color = COLOR_BLACK;
// }

// rbtree_TYPE_node *rbtree_TYPE_find(rbtree_TYPE *tree, TYPE data) {
//   rbtree_TYPE_node *node = tree->root;
//   while (node != tree->nil) {
//     if (TYPE_cmp(data, node->data) < 0) {
//       node = node->left;
//     } else if (TYPE_cmp(data, node->data) > 0) {
//       node = node->right;
//     } else {
//       return node;
//     }
//   }
//   return tree->nil;
// }


// void rbtree_TYPE_insert_node(rbtree_TYPE *tree, rbtree_TYPE_node *z) {
//   rbtree_TYPE_node *y = tree->nil;
//   rbtree_TYPE_node *x = rbtree_TYPE_find(tree, z->data);
//   if (x != NULL) {
//     return;
//   }
//   z->parent = y;
//   if (y == tree->nil) {
//     tree->root = z;
//   } else if (TYPE_cmp(z->data, y->data) < 0) {
//     y->left = z;
//   } else {
//     y->right = z;
//   }

//   z->left = tree->nil;
//   z->right = tree->nil;
//   z->color = COLOR_RED;

//   // rbtree_TYPE_insert_node_fixup(tree, z);
// }

// void rbtree_TYPE_insert(rbtree_TYPE *tree, TYPE data) {
//   rbtree_TYPE_node* z = (rbtree_TYPE_node*)malloc(sizeof(rbtree_TYPE_node));
//   z->data = data;
//   rbtree_TYPE_insert_node(tree, z);
// }

// void rbtree_TYPE_remove_node_fixup(rbtree_TYPE *tree, rbtree_TYPE_node *x) {
//   while ((x != tree->root) && (x->color == COLOR_BLACK)) {
//     if (x == x->parent->left) {

//       rbtree_TYPE_node *w = x->parent->right;
//       if (w->color == COLOR_RED) {
//         w->color = COLOR_BLACK;
//         x->parent->color = COLOR_RED;

//         rbtree_TYPE_left_rotate(tree, x->parent);
//         w = x->parent->right;
//       }

//       if ((w->left->color == COLOR_BLACK) && (w->right->color == COLOR_BLACK)) {
//         w->color = COLOR_RED;
//         x = x->parent;
//       } else {

//         if (w->right->color == COLOR_BLACK) {
//           w->left->color = COLOR_BLACK;
//           w->color = COLOR_RED;
//           rbtree_TYPE_right_rotate(tree, w);
//           w = x->parent->right;
//         }

//         w->color = x->parent->color;
//         x->parent->color = COLOR_BLACK;
//         w->right->color = COLOR_BLACK;
//         rbtree_TYPE_left_rotate(tree, x->parent);
//         x = tree->root;
//       }
//     } else {
//       rbtree_TYPE_node *w = x->parent->left;
//       if (w->color == COLOR_RED) {
//         w->color = COLOR_BLACK;
//         x->parent->color = COLOR_RED;
//         rbtree_TYPE_right_rotate(tree, x->parent);
//         w = x->parent->left;
//       }

//       if ((w->left->color == COLOR_BLACK) && (w->right->color == COLOR_BLACK)) {
//         w->color = COLOR_RED;
//         x = x->parent;
//       } else {
//         if (w->left->color == COLOR_BLACK) {
//           w->right->color = COLOR_BLACK;
//           w->color = COLOR_RED;
//           rbtree_TYPE_left_rotate(tree, w);
//           w = x->parent->left;
//         }

//         w->color = x->parent->color;
//         x->parent->color = COLOR_BLACK;
//         w->left->color = COLOR_BLACK;
//         rbtree_TYPE_right_rotate(tree, x->parent);

//         x = tree->root;
//       }
//     }
//   }
//   x->color = COLOR_BLACK;
// }

// rbtree_TYPE_node *rbtree_TYPE_remove_node(rbtree_TYPE *tree, rbtree_TYPE_node *z) {
//   rbtree_TYPE_node *y = tree->nil;
//   rbtree_TYPE_node *x = tree->nil;

//   if ((z->left == tree->nil) || (z->right == tree->nil)) {
//     y = z;
//   } else {
//     y = rbtree_TYPE_successor(tree, z);
//   }

//   if (y->left != tree->nil) {
//     x = y->left;
//   } else if (y->right != tree->nil) {
//     x = y->right;
//   }

//   x->parent = y->parent;
//   if (y->parent == tree->nil) {
//     tree->root = x;
//   } else if (y == y->parent->left) {
//     y->parent->left = x;
//   } else {
//     y->parent->right = x;
//   }
//   if (y != z) {
//     z->data = y->data;
//   }
//   if (y->color == COLOR_BLACK) {
//     rbtree_TYPE_remove_node_fixup(tree, x);
//   }
//   return y;
// }

// void rbtree_TYPE_remove(rbtree_TYPE* tree, TYPE data) {
//   rbtree_TYPE_node* n = rbtree_TYPE_find(tree, data);
//   if (n == NULL) {
//     return;
//   }
//   rbtree_TYPE_remove_node(tree, n);
// }